package com.yt.ds.chapter2;

import com.yt.ds.util.SortUtil;

/**
 * @Author: lzf
 * @Date: 2020/7/15 09:52
 * @Description: 基于堆的优先队列 [最大堆] [pq[0] 不存数据]
 */
public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N = 0;

    public MaxPQ(int maxN) {
        this.pq = (Key[]) new Comparable[maxN + 1];
    }

    public MaxPQ(Key[] pq) {
        this.pq = (Key[]) new Comparable[pq.length + 1];
        this.N = pq.length;
        for (int i = 0; i < pq.length; i++) {
            this.pq[i + 1] = pq[i];
        }
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int getSize() {
        return N;
    }

    public void insert(Key v) {
        pq[++N] = v;
        swim(N);
    }

    public Key delMax() {
        Key max = pq[1];
        exch(1, N);
        pq[N] = null;
        N = N - 1;
        sink(1, N);
        return max;
    }

    private boolean less(int i, int j) {
        return SortUtil.less(pq, i, j);
    }

    public void exch(int i, int j) {
        SortUtil.exch(pq, i, j);
    }

    /**
     * 上浮
     */
    public void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k / 2, k);
            k = k / 2;
        }
    }

    /**
     * 下沉
     */
    public void sink(int k, int n) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(j, j + 1)) {
                j = j + 1;
            }
            if (!less(k, j)) {
                break;
            }
            exch(k, j);
            k = j;
        }
    }

    public void display() {
        SortUtil.display(pq);
    }

    public Key[] getPq() {
        return pq;
    }
}
